package stringProblem;

/*
KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。
说简单点就是我们平时常说的关键字搜索。
模式串就是关键字（接下来称它为P），
如果它在一个主串（接下来称为T）中出现，
就返回它的具体位置，否则返回-1（常用手段）。

https://www.cnblogs.com/yjiyjige/p/3263858.html  KMP算法详细说明 包含代码
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 算法思路 不包含代码
*/

public class KMP {

    //暴力解法   在源字符串中找到是否存在目标字符串
    //复杂度 O（M * N） 字符串长度相乘
    public static int bl(String source , String target){
        //源字符串和目标字符串
        char[] sour = source.toCharArray();
        char[] tar = target.toCharArray();

        //源char数组的指针
        int i = 0;
        //目标char数组的指针
        int j = 0;

        //当不越界的时候 判断char字符是否相等
        while( i < sour.length && j < tar.length){
            //char字符相等共同加一，比较下一个字符是否相等
            if( sour[i] == tar[j] ){
                i++;
                j++;
            } else {
                //不相等的char，将指针回溯到源字符串的初始位置，然后加1，从下个位置开始判断
                i = i-j+1;
                //目标字符串回到头。重新开始判断
                j = 0;
            }
        }
        //如果是目标字符串的指针走完 。证明存在。
        if( j == tar.length){
            //返回一开始判定的位置。
            return i - j;
        }else {
            //不存在
            return -1;
        }
    }
    
    
    //KMP算法 专门解决字符串匹配的问题 
    public static int kmp(String ts,String ps){
        char[] t = ts.toCharArray();

        char[] p = ps.toCharArray();

        int i = 0; // 主串的位置

        int j = 0; // 模式串的位置

        int[] next = getNext(ps);

        while (i < t.length && j < p.length) {

            if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0

                i++;

                j++;

            } else {

                // i不需要回溯了

                // i = i - j + 1;

                j = next[j]; // j回到指定位置

            }

        }

        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }
    }
    
    //求NEXT[]数组 ,记录当前的字符前缀和后缀有几个共同的字符. --- 求的是关键字字符串
    public static int[] getNext(String target){
        char[] arr = target.toCharArray();
        int[] next = new int[arr.length];

        next[0] = -1;
        int j = 0 ;
        int k = -1 ;

        while ( j < arr.length-1 ){
            if( k == -1 || arr[j] == arr[k] ){
                next[++j] = ++k;
            }else{
                k = next[k];
            }
        }

        return next;
    }

    public static void main(String[] args) {
        String source = "SSSSSSSSSSSSSA";
        String target = "SSSA";
        System.out.println(bl(source,target));
        System.out.println(kmp(source,target));
        //int[] next = getNext("ABAC");
    }

}
